package skewreduce.lib;

import java.io.DataInput;
import java.io.DataOutput;
import java.io.IOException;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import org.apache.hadoop.io.Writable;

public class Cube implements Writable,Iterable<Cube> {
    private long  id;
    private Point3D mp;
    private Point3D Mp;
    // only set when current object is used as root and never change
    private int     numUnitCubes;
    private float[] splits;  // x, 2 * y, 4 * z
    private Cube[]  subCubes;

    public Cube() {}

    public Cube(long i,float sz) {
        id = i;
        float half = sz * 0.5f;
        mp = new Point3D(-half,-half,-half);
        Mp = new Point3D(half,half,half);
    }

    public Cube(long i,Point3D mpt,Point3D Mpt) {
        id = i;
        mp = mpt;
        Mp = Mpt;
    }

    public Cube(String spec) {
        String[] terms = spec.split(";");
        if ( terms == null || terms.length != 3 )
            throw new IllegalArgumentException(spec);
        id = Long.parseLong(terms[0]);
        mp = new Point3D(terms[1]);
        Mp = new Point3D(terms[2]);
    }

    public Point3D getMinPoint() { return mp; }
    public Point3D getMaxPoint() { return Mp; }
    public boolean isUnitCube()      { return subCubes == null; }
    public int     getNumUnitCubes() { return numUnitCubes; }

    private Cube getSubCube(int i) { return subCubes[i]; }

    public <T extends Point3D> boolean contains(T p) {
        return mp.getX() <= p.getX() && p.getX() <= Mp.getX()
                && mp.getY() <= p.getY() && p.getY() <= Mp.getY()
                && mp.getZ() <= p.getZ() && p.getZ() <= Mp.getZ();
    }

    public <T extends Point3D> boolean atCore(T p,float eps) {
        return mp.getX()+eps < p.getX() && p.getX() < Mp.getX()-eps
                && mp.getY()+eps < p.getY() && p.getY() < Mp.getY()-eps
                && mp.getZ()+eps < p.getZ() && p.getZ() < Mp.getZ()-eps;
    }

    public <T extends Point3D> boolean atSkin(T p,float eps) {
        return ! atCore(p,eps);
    }

    public <T extends Point3D> int getPartition(T x) {
        int part = 0;
        Cube node = this;
        while ( ! node.isUnitCube() ) {
            int child = node.getSubCubeID(x);
            part = ( part << 3 ) | child;
            node = node.getSubCube(child);
        }
        return part;
    }

    public <T extends Point3D> int getSubCubeID(T x) {
        if ( splits == null ) return -1;   // there is no subcubes

        if ( splits.length == 3 ) {
            if ( x.getX() < splits[0] ) {
                if ( x.getY() < splits[1] ) {
                    if ( x.getZ() < splits[2] ) {
                        return 0;
                    } else {
                        return 1;
                    }
                } else {
                    if ( x.getZ() < splits[2] ) {
                        return 2;
                    } else {
                        return 3;
                    }
                }
            } else {
                if ( x.getY() < splits[1] ) {
                    if ( x.getZ() < splits[2] ) {
                        return 4;
                    } else {
                        return 5;
                    }
                } else {
                    if ( x.getZ() < splits[2] ) {
                        return 6;
                    } else {
                        return 7;
                    }
                }
            }
        } else {
            if ( x.getX() < splits[0] ) {
                if ( x.getY() < splits[1] ) {
                    if ( x.getZ() < splits[3] ) {
                        return 0;
                    } else {
                        return 1;
                    }
                } else {
                    if ( x.getZ() < splits[4] ) {
                        return 2;
                    } else {
                        return 3;
                    }
                }
            } else {
                if ( x.getY() < splits[2] ) {
                    if ( x.getZ() < splits[5] ) {
                        return 4;
                    } else {
                        return 5;
                    }
                } else {
                    if ( x.getZ() < splits[6] ) {
                        return 6;
                    } else {
                        return 7;
                    }
                }
            }
        }
    }

    public <T extends Point3D> boolean notContains(T p) {
        return ! contains(p);
    }

    public Cube[] split() {
        return split(new Point3D(
                    (mp.getX()+Mp.getX())*0.5f,
                    (mp.getY()+Mp.getY())*0.5f,
                    (mp.getZ()+Mp.getZ())*0.5f));
    }

    // split cube at point x. uniform split.
    public <T extends Point3D> Cube[] split(T x) {
        assert contains(x); // x must be within this cube
        assert subCubes == null && splits == null;

        splits = new float[] { x.getX(), x.getY(), x.getZ() };

        subCubes = new Cube[] {
            new Cube((id << 3)|0,new Point3D(mp),new Point3D(x)),
            new Cube((id << 3)|1,new Point3D(mp.getX(),mp.getY(),x.getZ()),new Point3D(x.getX(),x.getY(),Mp.getZ())),
            new Cube((id << 3)|2,new Point3D(mp.getX(),x.getY(),mp.getZ()),new Point3D(x.getX(),Mp.getY(),x.getZ())),
            new Cube((id << 3)|3,new Point3D(mp.getX(),x.getY(),x.getZ()),new Point3D(x.getX(),Mp.getY(),Mp.getZ())),
            new Cube((id << 3)|4,new Point3D(x.getX(),mp.getY(),mp.getZ()),new Point3D(Mp.getX(),x.getY(),x.getZ())),
            new Cube((id << 3)|5,new Point3D(x.getX(),mp.getY(),x.getZ()),new Point3D(Mp.getX(),x.getY(),Mp.getZ())),
            new Cube((id << 3)|6,new Point3D(x.getX(),x.getY(),mp.getZ()),new Point3D(Mp.getX(),Mp.getY(),x.getZ())),
            new Cube((id << 3)|7,new Point3D(x),new Point3D(Mp))
        };

        return subCubes;
    }

    public void write(DataOutput out) throws IOException {
        out.writeLong(id);
        mp.write(out);
        Mp.write(out);
        out.writeInt(numUnitCubes);
        if ( splits == null ) {
            out.writeByte((byte)0);
        } else {
            out.writeByte((byte)splits.length);
            for ( float p : splits )
                out.writeFloat(p);
        }
        if ( subCubes == null ) {
            out.writeByte((byte)0);
        } else {
            out.writeByte((byte)subCubes.length);
            for ( Cube c : subCubes )
                c.write(out);
        }
    }

    public void readFields(DataInput in) throws IOException {
        id = in.readLong();
        mp = Point3D.read(in);
        Mp = Point3D.read(in);
        numUnitCubes = in.readInt();
        byte sz = in.readByte();
        if ( sz == 0 ) {
            splits = null;
        } else {
            splits = new float[sz];
            for ( int i = 0; i < sz; ++i )
                splits[i] = in.readFloat();
        }
        sz = in.readByte();
        if ( sz == 0 ) {
            subCubes = null;
        } else {
            subCubes = new Cube[sz];
            for ( int i = 0; i < sz; ++i ) {
                subCubes[i] = Cube.read(in);
            }
        }
    }

    public static Cube read(DataInput in) throws IOException {
        Cube c = new Cube();
        c.readFields(in);
        return c;
    }

    private Cube getPartition2(int target,int part) {
        if ( isUnitCube() && part == target ) return this;
        if ( subCubes != null ) {
            part = part << 3;
            for ( int i = 0; i < subCubes.length; ++i, ++part ) {
                Cube x = subCubes[i].getPartition2(target,part|i);
                if ( x != null ) return x;
            }
        }
        return null;
    }

    public Cube getPartition(int partition) {
        return getPartition2(partition,0);
    }

    public String toString() {
        return String.format("%d;%s;%s",id,mp,Mp);
    }

    public Iterator<Cube> iterator() {
        if ( subCubes == null ) {
            List<Cube> empty = Collections.EMPTY_LIST;
            return empty.iterator();
        }
        return Arrays.asList(subCubes).iterator();
    }

    static int PREFIX_MASK[] = { 0x0, 0x4, 0x6, 0x7 };

    /*
    public Cube getSubCube(int prefix,int prefixBits) {
        // get a subcube represents subcubes sharing the prefix
        float x = Float.MAX_VALUE,X = Float.MIN_VALUE;
        float y = Float.MAX_VALUE,Y = Float.MIN_VALUE;
        float z = Float.MAX_VALUE,Z = Float.MIN_VALUE;

        // keep minimum, maximum for each components
        for ( int i = 0; i < subCubes.length; ++i ) {
            if ( (i & PREFIX_MASK[prefixBits]) == prefix ) {
                Point3D minPt = subCubes[i].getMinPoint();
                x = Math.min( minPt.getX(), x );
                y = Math.min( minPt.getY(), y );
                z = Math.min( minPt.getZ(), z );

                Point3D maxPt = subCubes[i].getMaxPoint();
                X = Math.max( maxPt.getX(), X );
                Y = Math.max( maxPt.getY(), Y );
                Z = Math.max( maxPt.getZ(), Z );
            }
        }

        return new Cube(mask,new Point3D(x,y,z),new Point3D(X,Y,Z));
    }
    */

    public Cube getSubCube(int n,int i) {
        assert n < numUnitCubes;
        int runLength = (int)(numUnitCubes / n);
        Cube min = getPartition(i*runLength);
        Cube max = getPartition((i+1)*runLength-1);
        return new Cube(i,min.getMinPoint(),max.getMaxPoint());
    }

    public Cube[] getSubCubes(int n) {
        assert n < numUnitCubes;
        Cube[] r = new Cube[n];
        int runLength = (int)(numUnitCubes / n);
        for ( int i = 0; i < n; ++i ) {
            Cube min = getPartition(i*runLength);
            Cube max = getPartition((i+1)*runLength-1);
            r[i] = new Cube(i,min.getMinPoint(),max.getMaxPoint());
        }
        return r;
    }


    private void uniformSplit2(int n) { 
        if ( n == 0 ) return;
        for ( Cube c : split() ) {
            c.uniformSplit(n-1);
        }
    }

    /**
     * @param n depth of recursive split
     */
    public void uniformSplit(int n) { 
        uniformSplit2(n);
        numUnitCubes = 1 << (n*3);
    }

    public void print(java.io.PrintStream out) {
        out.println(this);
        for ( Cube c : this ) {
            c.print(out);
        }
    }

    public static void main(String[] args) {
        Cube cube = new Cube(0,1.0f);
        cube.uniformSplit(3);

        cube.print(System.out);

        Point3D[] testCases = new Point3D[] {
            new Point3D(0.1f,0.1f,0.1f),
            new Point3D(0.3f,0.3f,0.3f),
            new Point3D(-0.2f,0.1f,-0.4f),
            new Point3D(-0.49f,-0.49f,-0.49f),
            new Point3D(0.49f,0.49f,0.49f),
            new Point3D(0.007533f,-0.024684f,-0.467711f)
        };

        for ( Point3D p : testCases ) {
            System.out.printf("%s -> %d\n",p,cube.getPartition(p));
        }

        for ( int i = 0; i < 8; ++i )
            System.out.printf("%d -> %s\n",i,cube.getPartition(i));

        // test getSubCube

//       System.out.println(cube.getSubCube(0,1));
//       System.out.println(cube.getSubCube(4,1));

        System.out.println(cube.getSubCube(8,0));
        System.out.println(cube.getSubCube(8,1));
        System.out.println(cube.getSubCube(8,2));
        System.out.println(cube.getSubCube(8,3));
//        System.out.println(cube.getSubCube(8,4));
    }
}
